class Solution {
public:
    int countSubstrings(string s) {
        int m = s.size();
        vector<vector<bool>>dp(m, vector<bool>(m));
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = i; j < m; j++)
            {
                if (s[j] != s[i])
                {
                    dp[i][j] = false;

                }
                else
                {
                    if (i == j)
                    {
                        dp[i][j] = true;
                    }
                    else if (j - i == 1)
                    {
                        dp[i][j] = true;

                    }
                    else
                    {
                        dp[i][j] = dp[i + 1][j - 1];
                    }

                }

            }
        }
        int  count = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (dp[i][j])count++;
            }

        }
        return count;

    }
}; class Solution {
public:
    string longestPalindrome(string s) {
        int m = s.size();
        int lenth = 0;
        int memi;
        vector<vector<bool>>dp(m, vector<bool>(m));
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = i; j < m; j++)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                if (dp[i][j] && j - i + 1 > lenth)
                {
                    lenth = j - i + 1;
                    memi = i;
                }

            }
        }
        return s.substr(memi, lenth);
    }
}; class Solution {
public:
    bool checkPartitioning(string s) {
        int m = s.size();
        vector<vector<bool>>dp(m, vector<bool>(m));
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = i; j < m; j++)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
            }
        }
        for (int i = 1; i < m - 1; i++)
        {
            for (int j = i; j < m - 1; j++)
            {
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][m - 1])
                    return true;





            }
        }
        return false;







    }
}; class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int m = s.size();
        vector<vector<int>>dp(m, vector<int>(m));
        for (int i = 0; i < m; i++)
        {
            dp[i][i] = 1;
        }
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = i + 1; j < m; j++)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = dp[i + 1][j - 1] + 2;


                }
                else
                {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);



                }






            }
        }

        return dp[0][m - 1];
    }
};